package com.yitiao.data_algorithms.leetcode.editor.cn;

class RotateFunction {
    // 2023-02-06 13:49:41
    public static void main(String[] args) {
        Solution solution = new RotateFunction().new Solution();
    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 根本采用动态规划别的思想，即如何根据F(0)算出F(1):
     * - 找出递推公式
     * - 优化计算差值 -> 前缀和
     * <p>
     * 题目要对「旋转数组」做逻辑，容易想到将数组进行复制拼接，
     * 得到长度为2n的新数组，在新数组上任意一个长度为n的滑动窗口都对应了一个旋转数组。
     */
    class Solution {
        public int maxRotateFunction(int[] nums) {
//            return extracted(nums);
            // 动态规划 dp[i]=dp[i-1]+sum-n*n[n-i]
            int n = nums.length;
            int[] dp = new int[n];
            int sum = 0;
            for (int i = 0; i < n; i++) {
                dp[0] += i * nums[i];
                sum += nums[i];
            }
            int ans = dp[0];
            for (int i = 1; i < n; i++) {
                dp[i] = dp[i - 1] + sum - n * nums[n - i];
                ans = Math.max(dp[i], ans);
            }
            return ans;
        }

        // 前缀和+滑动窗口
        private int extracted(int[] nums) {
            int n = nums.length;
            // 计算复制后数组的前缀和
            int[] sum = new int[n * 2 + 10];
            for (int i = 1; i <= 2 * n; i++)
                sum[i] = sum[i - 1] + nums[(i - 1) % n];

            int ans = 0;
            // 计算F(0)
            for (int i = 1; i <= n; i++)
                ans += nums[i - 1] * (i - 1);
            // 计算F(n)
            for (int i = n + 1, cur = ans; i < 2 * n; i++) {
                cur += nums[(i - 1) % n] * (n - 1);
                cur -= sum[i - 1] - sum[i - n];
                if (cur > ans) ans = cur;
            }
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}